[Conventional Certified Shuffling]
A conventional certified shuffling technique is described, for example, in Japanese Patent Application No. 2000-059091 (Japanese Patent Laid-Open Application No. 2001-251289) (hereinafter, referred to as “Document 1”).
FIG. 6 is a block diagram showing a configuration of the conventional technique described in Document 1. In each of the accompanying drawings, a joining arrow means that pieces of information at the roots of the arrow are sent together to the tip of the joining arrow, while a branched arrow means that at least part of the information at the root of the arrow is sent to the tips of the branched arrow.
The term “shuffling” used herein is referred to as “re-encryption shuffling” in Document 1. Herein, “shuffling” means to shuffle the order of the input encrypted texts and to re-encrypt them.
Referring to FIG. 6, first, encrypted texts/public keys 100 are input to be shuffled at the shuffling step 101. At this point, the input encrypted texts and shuffling information 102 specifying the shuffling are sent to the identical conversion certifying step 103 as well as to the substitution certifying step 104. The identical conversion certifying step 103 generates and outputs identical conversion certificates 105, and sends random numbers 106 used for generating the certificates 105 to the substitution certifying step 104. The substitution certifying step 104 outputs substitution certificates 107. The identical conversion certificates 105, the substitution certificates 107, the encrypted texts/public keys 100, and shuffled encrypted texts 109 are input to the response generating step 108, where responses are added to the identical conversion certificates 105, the substitution certificates 107 and the encrypted texts to generate and output shuffling certificates 110.
The identical conversion certificates 105 together with the responses prove that they have the knowledge of the order of the shuffled input texts and the content of conversion for encryption, and, when the input encrypted texts each contain multiple integer elements, prove that the elements of each encrypted text are shuffled in the same order and received are subjected to corresponding encryption. The substitution certificates 107 together with the responses prove that the shuffling order of the input encrypted texts is correct.
In order to prove that this shuffling process is correct, two certificating steps, namely the identical conversion certificating step and the substitution certificating step, are employed in Document 1. Document 1 achieves efficient generation of shuffling certificates by separating the processed subjects of the certifying step.
[Conventional Certified Decryption]
A conventional technique for certified decryption is disclosed, for example, in Japanese Patent Application No. 08-263575 (Japanese Patent No. 3003771) (hereinafter, referred to as “Document 2”).
FIG. 7 is a block diagram showing a configuration of the conventional technique disclosed in Document 2. Referring to FIG. 7, shuffled encrypted texts 200 and secret keys 201 are first input into the decrypting step 203 for decryption. Then, the input shuffled encrypted texts 200, the secret keys 201 and the decrypted texts 204 are sent to the decryption certifying step 205. Based on these information, the decryption certifying step 205 outputs decryption certificates 206.
Herein, “decryption” means to partially decrypt the encrypted texts by using at least one of the secret keys that are kept separately from each other. By repeating such partial decryption by using all of the secret keys, the encrypted texts can be decrypted completely.
[Certified Shuffle-decrypting Method]
The certified shuffling technique of Document 1 and the certified decrypting technique of Document 2 can be combined to obtain a certified shuffle-decrypting method.
FIG. 8 is a block diagram for illustrating the certified shuffle-decrypting method by simply combining the techniques of Documents 1 and 2. This method is characterized in that shuffled encrypted texts 304 are contained in shuffle-decryption certificates 316, that the shuffled encrypted texts 304 are input into decryption certifying step 314 and that no data is transformed from the response generating step to the decryption certifying step.
However, this technique has the following problems.
Assume a system in which the encrypted texts are input to be shuffled and decrypted to give decrypted texts, and then validation certificates for the shuffling/decrypting process are generated and output. Although an anonymous communication channel can be configured by combining the techniques of Documents 1 and 2 as described above, this method requires unnecessary shuffled encrypted texts to be output to prove validation. When there are a number of encrypted texts, outputting unnecessary shuffled encrypted texts adversely increases the amount of certificates and deteriorates communication efficiency.
According to the technique of Document 2, modular exponentiations accompanied by a large amount of calculation proportional to the number of the encrypted texts have to be carried out for generating the certificates. This adversely affects efficiency of the shuffle-decryption.
In view of the drawbacks of the above-described techniques, a first objective of the present invention is to combine the techniques of Documents 1 and 2 to provide a certified shuffle-decrypting system, a certified shuffle-decrypting method and a shuffle-decryption verifying method, which are efficient since there is no need of outputting shuffled encrypted texts and thus an amount of calculation as well as an amount of certificates are minimized.
In view of the drawbacks of the above-described techniques, a second objective of the present invention is to provide a certified shuffle-decrypting system, a certified shuffle-decrypting method, which can realize further high-speed processing by greatly decreasing the number of modular exponentiations and an amount of calculation.